package com.zx._12_算法.algorithm.letcode;

import java.util.HashMap;

public class Demo3 {

    public static void main(String[] args) {

    }

    public Node copyRandomList(Node head) {

        // key = node.data, value = node; 保存新创建的数据
        HashMap<Integer, Node> map = new HashMap<Integer, Node>();
        Node newHead = new Node(head.val);
        // 先创建单链
        Node node = head;
        Node newNode = newHead;
        map.put(newHead.val, newHead);
        while (node != null) {
            Node create = new Node(node.val);
            newNode.next = create;

            node = node.next;
            newNode = create;

            map.put(create.val, create);
        }

        node = head;
        newNode = newHead;
        while (node != null) {
            Node random = node.random;
            if (random != null) {
                Node randomGet = map.get(random.val);
                newNode.random = randomGet;
            }

            node = node.next;
            newNode = newNode.next;
        }

        newNode = newHead;
        System.out.println("[");
        while (newNode != null) {
            System.out.println("[" + newNode.val + "," + "]");
            newNode = newNode.next;
        }
        System.out.println("]");
        return newNode;
    }


    class Node {

        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
